#include <iostream>

// 哈夫曼树节点定义
struct HuffmanNode 
{
    HuffmanNode(int w)
        : weight(w)
        , left(nullptr)
        , right(nullptr)
    {
    }
    int weight;  //权重
    HuffmanNode* left; //左孩子
    HuffmanNode* right; //右孩子
    
};

//选出两个权重最低的索引
void selectTwoMinNodes(HuffmanNode* nodes[], int size, int& min1, int& min2)
{
    min1 = -1;
    min2 = -1;

    for (int i = 0; i < size; ++i) {
        if (nodes[i] != nullptr) 
        {
            if (min1 == -1 || nodes[i]->weight < nodes[min1]->weight) 
            {
                min2 = min1;
                min1 = i;
            } 
            else if (min2 == -1 || nodes[i]->weight < nodes[min2]->weight) 
            {
                min2 = i;
            }
        }
    }
}

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(int* weights, int size)
{
    HuffmanNode* nodes[100]; // 假设最多100个节点
    int n = size;

    // 初始化节点数组
    for (int i = 0; i < n; ++i) 
    {
        nodes[i] = new HuffmanNode(weights[i]);
    }

    for (int i = 0; i < n - 1; ++i) 
    {
        int min1, min2;
        selectTwoMinNodes(nodes, n, min1, min2);

        // 创建新节点，并合并两个最小权重的节点
        HuffmanNode* newNode = new HuffmanNode(nodes[min1]->weight + nodes[min2]->weight);
        newNode->left = nodes[min1];
        newNode->right = nodes[min2];

        // 标记已经合并的节点
        nodes[min1] = newNode;
        nodes[min2] = nullptr;
    }

    // 返回根节点
    for (int i = 0; i < n; ++i) 
    {
        if (nodes[i] != nullptr) {
            return nodes[i];
        }
    }

    return nullptr;
}

void PrevPrint(HuffmanNode* root)
{
    if (root == nullptr) 
        return;
    std::cout << root->weight << " ";
    PrevPrint(root->left);
    PrevPrint(root->right);
}

void MidPrint(HuffmanNode* root)
{
    if (root == nullptr)
        return;
    MidPrint(root->left);
    std::cout << root->weight << " ";
    MidPrint(root->right);
}

int main()
{
    int weights[] = { 5, 9, 12, 13, 16, 45 };
    int size = sizeof(weights) / sizeof(weights[0]);

    HuffmanNode* root = buildHuffmanTree(weights, size);
    PrevPrint(root);
    std::cout << std::endl;
    MidPrint(root);
    std::cout << std::endl;

    return 0;
}